package com.jn.algorithm.day025.question79;

/**
 * @author 江南大学1033190417
 * @date 2022/5/16 12:57
 */
public class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == word.charAt(0)) {
                    if (dfs(board, word, i, j, 0)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] board, String word, int i, int j, int cur) {
        if (cur == word.length()) {
            return true;
        }
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length) {
            return false;
        }
        //如果当前不相等则剪枝
        if (board[i][j] != word.charAt(cur)) {
            return false;
        }
        //上下左右四个方向走
        char t = board[i][j];
        board[i][j] = '0';//标记当前走过
        boolean res =
                dfs(board, word, i + 1, j, cur + 1) ||
                        dfs(board, word, i - 1, j, cur + 1) ||
                        dfs(board, word, i, j + 1, cur + 1) ||
                        dfs(board, word, i, j - 1, cur + 1);
        board[i][j] = t;
        return res;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        char[][] board = new char[][]{
                {'A', 'B', 'C', 'E'},
                {'S', 'F', 'C', 'S'},
                {'A', 'D', 'E', 'E'}
        };
        String word = "SEE";
        System.out.println(solution.exist(board, word));
    }
}
